import java.util.Stack;

/*
 * @lc app=leetcode.cn id=84 lang=java
 *
 * [84] 柱状图中最大的矩形
 */

// @lc code=start
class Solution {
    //暴力法
    public int largestRectangleArea0(int[] heights) {
        int area = 0;
        int n = heights.length;

        for(int i =0;i<n;i++){
            int j=i;
            int w=1,h=heights[i];//高就是这个了，宽初始为1
            while(--j>=0 && heights[j]>=h){
                w++;
            }
            j=i;
            while(++j<n && heights[j]>=h){
                w++;
            }
            area = Math.max(area, w*h);
        }

        return area;
    }
// 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」；
// 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
// 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面
    public int largestRectangleArea(int[] heights) {
        int temp[] = new int[heights.length+2];
        System.array(heights, 0, temp, 1, heights.length);
        //前后加一个0，方便处理，因为这样就不用考虑增序排列的情况。
        Stack<Integer> s = new Stack<>();
        int area=0;
        for(int i=0;i<temp.length;i++){
            while(!s.isEmpty() && temp[i]<temp[s.peek()] ){
                int h = temp[s.pop()];//拿到h
                //下一个才是左边第一个小于它的
                area = Math.max(area, h*(i-s.peek()-1));
            }
            s.push(i);
        }

        return area;

    }
}
// @lc code=end

